import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class L131 {
    public static void main(String[] args) {
        List<List<String>> aab = new Solution().partition("aab");
        for (List<String> strings : aab) {
            System.out.println(strings.toString());
        }
    }


    static class Solution {
        List<List<String>> result = new ArrayList<>();
        LinkedList<String> tmp = new LinkedList<String>();

        public List<List<String>> partition(String s) {
            int index = 0;
            backTracking(s, index, new StringBuilder());
            return result;
        }

        private void backTracking(String s, int index, StringBuilder sb) {
            if (index == s.length()) {
                result.add(new LinkedList<>(tmp));
                return;
            }

            for (int i = index; i < s.length(); i++) {
                sb.append(s.charAt(i));
                if (checkBack(sb)) {
                    tmp.add(sb.toString());
                    backTracking(s, i + 1, new StringBuilder());
                    tmp.removeLast();
                }
            }
        }

        private boolean checkBack(StringBuilder sb) {
            for (int i = 0; i < sb.length() / 2; i++) {
                if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)) {
                    return false;
                }
            }
            return true;
        }
    }

}
